package code;
import models.TreeNode;

public class reConstructBinaryTree {
    public TreeNode reConstructTree(int [] pre,int [] in) {
        return construct(pre,0,pre.length-1,in,0,in.length-1);
    }
    public TreeNode construct(int[] pre,int ps,int pe,int[] in,int is,int ie){
        if(ps>pe||is>ie){
            return null;
        }
        TreeNode root = new TreeNode(pre[ps]);
        int sep=0;
        for(int i=is;i<=ie;i++){
            if(in[i]==root.val){
                sep = i;
                break;
            }
        }
        root.left=construct(pre,ps+1,ps+sep-is,in,is,sep-1);
        root.right=construct(pre,ps+1+sep-is,pe,in,sep+1,ie);
        return root;

    }

    public static void main(String[] argv){
        int[] pre = new int[]{1,2,4,7,3,5,6,8};
        int[] in = new int[]{4,7,2,1,5,3,8,6};
        reConstructBinaryTree reconstructBinaryTree = new reConstructBinaryTree();
        reconstructBinaryTree.reConstructTree(pre, in);
    }
}
